Definition(s)

Voronoi diagram is a partitioning of a plane into regions based on distance to points in a specific subset of the plane.

Algorithm(s)



In [1]:

    
from PIL import Image, ImageDraw
from IPython.display import Image as PImage
import numpy as np
import math



In [14]:

    
def generate_voronoi_diagram(width, height, ncells, metric):
    image = Image.new("RGB", (width, height))
    imgx, imgy = image.size
    putpixel = image.putpixel
    draw = ImageDraw.Draw(image)
    
    points = []
    for i in range(ncells):
        x = np.random.randint(imgx)
        y = np.random.randint(imgy)
        r, g, b = np.random.randint(256, size=3)
        points.append((x, y, r, g, b))
        
    for xx in range(imgx):
        for yy in range(imgy):
            best, ind = float('inf'), -1
    
            for i in range(ncells):
                x, y, r, g, b = points[i]
                d = metric(x - xx, y - yy)
                
                if d < best:
                    best = d
                    ind = i
                    
            x, y, r, g, b = points[ind]            
            putpixel((xx, yy), (r, g, b))
            
    for point in points:
        x, y, r, g, b = point
        draw.ellipse((x-2, y-2, x+2, y+2), fill=(255,255,255))
    
    image.save("VoronoiDiagram.png", "PNG")

Run(s) using the Euclidean distance



In [16]:

    
generate_voronoi_diagram(500, 400, 30, math.hypot)
PImage("VoronoiDiagram.png")









    Out[16]:



In [4]:

    
generate_voronoi_diagram(1000, 1000, 100, math.hypot)
PImage("VoronoiDiagram.png")









    Out[4]:



In [5]:

    
generate_voronoi_diagram(1000, 1000, 500, math.hypot)
PImage("VoronoiDiagram.png")









    Out[5]:



In [9]:

    
generate_voronoi_diagram(300, 300, 3, math.hypot)
PImage("VoronoiDiagram.png")









    Out[9]:



In [12]:

    
generate_voronoi_diagram(600, 400, 10, math.hypot)
PImage("VoronoiDiagram.png")









    Out[12]:

Run(s) using Manhattan distance



In [19]:

    
generate_voronoi_diagram(600, 400, 10, lambda x, y: abs(x) + abs(y))
PImage("VoronoiDiagram.png")









    Out[19]:



In [20]:

    
generate_voronoi_diagram(1000, 1000, 500, lambda x, y: abs(x) + abs(y))
PImage("VoronoiDiagram.png")









    Out[20]:



In [28]:

    
generate_voronoi_diagram(500, 500, 10, lambda x, y: abs(x) + abs(y))
PImage("VoronoiDiagram.png")









    Out[28]:

Art ?



In [25]:

    
generate_voronoi_diagram(500, 500, 10, lambda x, y: abs(x) * abs(y))
PImage("VoronoiDiagram.png")









    Out[25]:



In [29]:

    
generate_voronoi_diagram(700, 500, 10, lambda x, y: abs(x) * abs(y))
PImage("VoronoiDiagram.png")









    Out[29]:



In [35]:

    
generate_voronoi_diagram(500, 500, 10, lambda x, y: abs(x) ** abs(y))
PImage("VoronoiDiagram.png")









    Out[35]:



In [36]:

    
generate_voronoi_diagram(500, 500, 250, lambda x, y: abs(x) * abs(y))
PImage("VoronoiDiagram.png")









    Out[36]:



In [37]:

    
generate_voronoi_diagram(500, 500, 250, lambda x, y: max(abs(x), abs(y)))
PImage("VoronoiDiagram.png")









    Out[37]:



In [39]:

    
generate_voronoi_diagram(800, 600, 25, lambda x, y: max(abs(x), abs(y)))
PImage("VoronoiDiagram.png")









    Out[39]:



In [40]:

    
generate_voronoi_diagram(800, 600, 25, lambda x, y: min(abs(x), abs(y)))
PImage("VoronoiDiagram.png")









    Out[40]:



In [42]:

    
generate_voronoi_diagram(850, 600, 100, lambda x, y: min(abs(x), abs(y)))
PImage("VoronoiDiagram.png")









    Out[42]: